The present invention relates generally to data communication systems and more particularly relates to a reduced latency interleaver/de-interleaver system adapted to utilize a shortened first codeword.
Digital data communications systems are currently being used more and more to transmit and receive data between remote locations. The reliability and integrity of the data being communicated is an important part of any data communications system. In the ideal case, the data being transmitted should be identical to the data being received at the receiving location. In reality, however the data received at the receiving location is oftentimes corrupted with respect to the original data transmitted. Any data communication errors arc usually attributed to one or more of the transmission equipment, transmission medium or receiving equipment. With respect to the transmission medium, these types of data errors are usually attributed to the less than ideal conditions associated with the particular transmission medium.
For example, communication systems designed to transmit and receive using power line carrier techniques are subjected to the non-optimum conditions imposed by the power line medium. The power line medium is an unstable medium characterized by much pulse noise, continuous wave interference and impedance modulation. Depending on the length of the symbols used to transmit packets, the channel may not be assumed to be static during a packet time.
Consider a relatively long symbol time of 800 xcexcsec. In this case, the power line channel cannot be assumed to be statistically static during a packet time. In cases such as this, some kind of error correcting code (ECC) is typically employed. Data communications systems often rely on error detection or error correction schemes to detect the occurrence of a data error or to correct a data error. As is known by practical tests, the most critical problem imposed by the power line that a modem must deal with is impedance modulation. The power line impedance modulation way be modeled as signal elimination at a 20% duty cycle periodically at a rate of 100 Hz for a 50 Hz AC line or 120 Hz for a 60 Hz AC line. Thus, any error correcting code employed must be robust enough to overcome this problem.
One simple form of error detection is the use of a parity bit associated with each block of data to indicate whether the particular block contains an odd or even number of xe2x80x981xe2x80x99 bits. This is a simple type of error detection scheme capable of accurately detecting only up to one bit error per data block. The use of a parity bit, however, cannot detect the occurrence of two bit errors in a data block, since this is not detected as a parity violation. Additionally, a single parity bit can only detect errors, it cannot correct any errors. When an error is detected, the receiver requests retransmission of the particular data block from the transmitter.
Another well known correction and/or detection scheme involves the use of binary block codes. Specifically, an (n, k, d) binary block code is a set of 2k binary codewords of block length n and minimum coding distance d. The data to be transmitted is first partitioned into binary blocks of length k, then each block is mapped into a binary codeword of length n, which is then modulated and transmitted onto the channel. Such a block code is capable of correcting up to t=(dxe2x88x921)/2 errors within each codeword.
The problem of burst errors may be overcome by the use of interleaving. Power line channel errors may occur in bursts, the length of which may exceed the error correction capability of the code. Interleaving the data stream before it is modulated and transmitted over the channel may help to overcome burst errors. An interleaver is a memory device used to rearrange and separate the codewords to be transmitted. Thus, if an error burst occurs during transmission of a packet, the error burst will not be localized to one particular codeword. Rather, the errors will be spread across several codewords. If the errors were completely within one codeword, they may exceed the number of errors that the system can correct by the use of a block code. By smearing the data errors across several codewords, the number of errors within each codeword will be reduced such that the ECC is capable of correcting the errors.
At the transmitter, the interleaver functions to rearrange the data within the codewords while at the receiver, the de-interleaver essentially performs the reverse process to reconstruct the codewords for subsequent use. This type of interleaving, referred to as block interleaving, introduces latency due to the fact that a complete block has to be written before it can be read.
A diagram illustrating the input and output data of an example prior art 2:1 block interleaver is shown in FIG. 1. In this example, codewords of length 9 symbols we input to an interleaves. Each codeword is made up of 7 data symbols and two parity symbols. The interleaver has a block size of 2 codewords. Thus, the interleaver input block buffer is filled with two codewords, gay referenced 10, which are then 2:1 interleaved. The output is shown by the symbol buffer 12. The symbols of the first codeword are denoted by the xe2x80x981xe2x80x99s and the symbols of the second codeword by the xe2x80x982xe2x80x99s. Each codeword also comprises two parity symbols denoted generally Pnk where k denotes the codeword number and n denotes the parity symbol number.
Without interleaving, the first codeword arrives at the receiver after one codeword time. Since no interleaving was used, the symbols received represent the complete codeword that can be immediately decoded. With the use of interleaving, receipt of the last symbol of the first codeword does not occur until the 17th symbol, at which time it may be passed to the decoder. The last symbol of the second codeword arrives one symbol later. Thus, the first codeword suffers from latency of almost an entire codeword.
The latency caused by conventional interleavers may be problematic depending on the requirements of the particular communications system and the protocol(s) used therewith. For some systems, this latency is intolerable thus precluding the use of interleaving in the system.
There is thus a need for an interleaving scheme that is able to provide the benefits of interleaved transmission of data while reducing the latency of the system to a minimum or even eliminating it altogether.
The present invention is a novel and useful interleaver/de-interleaver mechanism for reducing the latency of transmitted interleaved codewords. The interleaver/de-interleaver mechanism utilizes a shortened first codeword which functions to offset the interleaving and transmission of subsequent codewords so as to achieve reduced latency depending on the degree of shortening applied. The mechanism of the present invention is useful in communication systems characterized by consecutively transmitted codewords made up of a plurality of symbols. The mechanism of the present invention is especially useful in communication systems that utilize the power line as the transmission medium. The interleaver/de-interleaver mechanism may be used in power line carrier based systems to reduce the exposure to burst errors by providing interleaving with minimal latency penalty.
The invention is operative to greatly reduce interleaver latency by the use of xe2x80x98symmetricxe2x80x99 interleaving whereby the first codeword is shortened thus permitting its availability at the receiver sooner than the normal latency of two codeword times. Depending on the modulation scheme employed, length of the codeword L and the degree of shortening, the first codeword may be available after only a single codeword time, thus exhibiting zero latency.
In operation, the interleaver is operative to shorten the first codeword by a certain amount U symbol The shortened first codeword is then interleaved with the second codeword. A portion of the third codeword is then interleaved with the latter portion of the second codeword. The interleaving process continues in this staggered fashion. The interleaved symbols generated are transmitted onto the channel.
At the receiver, the interleaved symbols are received and every block of L symbols is counted. After receipt of the first L symbols, the first shortened codeword can be de-interleaved and decoded. After receipt of the subsequent L symbols, the second codeword can be decoded. The shortened first codeword is reconstructed by assuming predetermined dummy symbols for the absent symbols. For example, the transmitter and receiver may be adapted to insert xe2x80x98zeroxe2x80x99 symbols into the U absent symbol places. Thus, the decoder at the receiver is unaware of the use of the shortened first codeword. Subsequent codewords are de-interleaved and decoded normally.
Many aspects of the previously described invention may be constructed as software objects that execute in embedded devices as firmware, software objects that execute as part of a software application on a computer system running an operating system such as Windows, UNIX, LINUX, etc., an Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA) or functionally equivalent discrete hardware components.
There is therefore provided in accordance with the present invention a method of interleaving a stream of codewords, each codeword having a length L symbols, the method comprising the steps of interleaving the last L-U symbols of a first codeword with the first L-U symbols of a second codeword, interleaving the first U symbols of a third codeword with the last U symbols of the second codeword, shortening the initial first codeword received in the stream of codewords by skipping over the first U symbols of the initial first codeword and wherein L and U are positive integers.
There is also provided in accordance with the present invention an interleaver for interleaving a stream of codewords, each codeword having a length L symbols, the method comprising the steps of means for interleaving the last L-U symbols of a first codeword with the first L-U symbols of a second codeword, means for interleaving the first U symbols of a third codeword with the last U symbols of the second codeword, means for shortening the initial first codeword received in the stream of codewords by discarding the first U symbols of the initial first codeword and wherein L and U are positive integers.
There is further provided in accordance with the present invention a method of de-interleaving a stream of symbols, the method comprising the steps of sequentially counting each received symbol, upon receipt of the first L symbols, de-interleaving and extracting L-U symbols to construct a first shortened codeword and upon receipt of each subsequent L symbols, de-interleaving and extracting L symbols to construct subsequent codewords.
There is also provided in accordance with the present invention a de-interleaver for de-interleaving a stream of symbols, the method comprising the steps of means for sequentially counting each received symbol, means for de-interleaving the first L symbols and for extracting L-U symbols therefrom so as to construct a first shortened codeword and means for de-interleaving subsequent groups of L symbols and for extracting L symbols from the previously received group of 2L symbols so as to construct subsequent codewords.
There is further provided in accordance with the present invention a modem transceiver for transmitting and receiving signals in a communications media based network comprising a coupling circuit for generating a receive signal received over the network and for outputting a transmit signal onto the network, a transmitter adapted to modulate data to be transmitted in accordance with a modulation scheme so as to generate a transmit waveform therefrom, the transmitter comprising an interleaver for interleaving a stream of codewords, each codeword having a length L symbols, the interleaver comprising means for interleaving the last L-U symbols of a first codeword with the first L-U symbols of a second codeword, means for interleaving the first U symbols of a third codeword with the last U symbols of the second codeword, means for shortening the initial first codeword received in the stream of codewords by discarding the first U symbols of the initial first cod wherein L and U are positive integers, a receiver adapted to demodulate the receive signal in accordance with the modulation scheme so as to generate a receive data signal therefrom, the receive comprising a de-interleaver for de-interleaving a stream of symbols, the de-interleaver comprising means for sequentially counting each received symbol, means for de-interleaving the first L symbols and for extracting L-U symbols therefrom so as to construct a first shortened codeword, means for de-interleaving subsequent groups of L symbols and for extracting L symbols from the previously received group of 2L symbols so as to construct subsequent codewords, a media access control (MAC) circuit adapted to interface an application processor to the shared communications media, the application processor adapted to control the operation of the transmitter, receiver and MAC and to provide an interface between the MAC and an external host.